//------AATreeZ.h------

/*
Intro.
本文件是 AA-树 数据结构实现。

这是我们课设系统最内层的核心数据结构，是一种自平衡二叉排序树，
它是红黑树的一种变种，支持以O(log2N)的时间操作树内元素。

为什么用到自平衡二叉排序树?

当我们对一个元素集合进行查找操作时，如果是普通的线性查找，
花费的时间是O(N)，如果我们将元素放进有序容器中排好序，
我们可以对元素集进行二分查找，花费的时间会降到O(log2N)。
而二叉排序树就是一种元素插入时就会自然产生顺序的数据结构，
所以对二叉排序树进行查找本质上就是进行二分查找，效率会大大提高。
二叉排序树会存在失衡的问题，最坏的情况下，每一个结点都只有左侧或者
右侧拥有子结点，此时二叉排序树退化成链表，操作时间也会自然退化为O(N)。
自平衡二叉树排序数据结构会在插入与删除时通过结点旋转、重新安排指针
等方式维护二叉排序树的平衡性，保证操作时间都在O(log2N)内。

我们的每一个实体(书，图画，光盘)的数据都会以结构体或者类的形式
以二进制的方式独立存放进不同的数据文件中，这些数据文件的文件名
就设定为实体的唯一编号，这样我们通过编号查询媒体库时，就可以直
接通过fstream对象的open函数找到它的数据文件，把在磁盘中查询
数据文件起始地址的任务交给了fstream与操作系统，它们可能是以
散列表或者一些其它映射方式实现的，理论上能保证查询操作在O(1)
左右，非常迅速。而如果以实体标题查询实体数据，就需要我们去建立
一个 标题->编号 的索引表(也就是string2ID_Index文件中定义的
titleInd类)去加快搜索(总不能一个个文件打开然后查看里面的标题
是否为用户所查询的吧)。借助于自平衡二叉树排序，就能保证我们按照
O(log2N)的时间去以实体的标题搜索到对应的编号，然后使用fstream
的open函数通过得到的编号去打开相应的数据文件。
*/

//防止重复文件包含
#ifndef AATREEZ_H
#define AATREEZ_H

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <string>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>

//ifdef _WINDOWS_
//pragma comment(lib,"x64/pthreadVC2.lib")
//endif

#define IOERROR "File I/O error."
#define MEMERROR "Memory error."

/*
这是对象化的 AA-树 数据结构封装，请不要忘记使用名称空间
MediaBaseManagement::DataStructure::AATree
*/

//undef NULL
//define NULL nullptr

//namespace MediaBaseManagement
//{
	namespace dataStructureZ
	{
		namespace AATree
		{
			template<class T>struct AANode
			{
/*
这是AA-树结点结构体的定义:
每一个AA-树结点拥有一个泛型数据域element，即结点存放的元素。
每一个AA-树结点同普通的二叉排序树一样拥有左子结点与右子结点指针。
每一个AA-树结点拥有一个用于存储该结点层次信息的level字段，这将
	被应用于平衡操作
	
拥有一个构造函数，每生成一个结点时，初始层次为1。
*/
				T				  element;
				struct AANode<T>* lChild;
				struct AANode<T>* rChild;
				unsigned char	  level;
				
				public:AANode<T>(void):level(1){}
			};
			
			template<class T>class AATreeZ
			{
/*
这是我们的AA-树管理对象，它封装了AA-树的各种操作
每一个AATreeZ对象拥有一个根结点指针与两个删除辅助变量

public:AATreeZ(void)																					01-构造函数
public:bool isEmpty(void)const																			02-判断树是否为空
public:void makeEmpty(void)																				04-清空树操作驱动函数&外部接口
public:void operator ~ (void)																			05-清空树对象运算符重载
public:virtual ~AATreeZ(void)																			06-析构函数，释放空间
public:T& find(const T&x) const																			09-寻找元素驱动函数，返回其引用
public:T& operator [] (const T&x) const																	10-寻找元素运算符重载，返回其引用
public:T&findMin(void)const																				15-寻找最小元素，并返回其引用
public:T&findMax(void)const																				16-寻找最大元素，并返回其引用 
public:T* insert(const T&x)																				22-插入元素操作驱动函数								若插入成功，返回NULL，如果待插入的元素已存在，返回其地址
public:AATreeZ<T>& operator << (const T& t)																23-插入元素操作运算符重载							注意这里返回的是本对象的引用 
public:AATreeZ<T>& del(const T& x,void(*funP)(const T&) = NULL,bool* deled = NULL)						25-删除元素操作驱动函数								删除是否成功通过deled所指向的布尔变量给出
public:void preOrder(void(*p)(const T&))const															27-先序遍历操作驱动函数								通过p所指向的函数对遍历到的结点进行操作 
public:void midOrder(void(*p)(const T&))const															30-中序遍历操作驱动函数								通过p所指向的函数对遍历到的结点进行操作 
public:void midOrder(std::ofstream &ofs,void(*p)(std::ofstream&,const T&))								31-中序遍历操作驱动函数(带文件流对象的)				通过p所指向的函数对遍历到的结点进行操作 
public:void postOrder(void(*p)(const T&))const															33-后序遍历操作驱动函数								通过p所指向的函数对遍历到的结点进行操作 
public:void reLevel(void)																				36-重新计算所有结点层次操作驱动函数					注意，前提是当前二叉树原本结构符合AA-树平衡条件 
public:void insertWithoutEnbalance(const T& ele)														37-不带平衡旋转的节点插入函数						适用于从以BFS的方式遍历已平衡的AA-树结点元素输出的文件中读取元素并重建AA-树
public:void bfsOrder(void(*p)(const T&))const															38-以广度优先搜索的方式遍历结点 					通过p所指向的函数对遍历到的结点进行操作 
public:void bfsOrder(std::deque<char *> & que,void(*p)(std::deque<char *>&, const T&))const				39-以广度优先搜索的方式遍历结点(带双端队列的)		通过p所指向的函数对遍历到的结点进行操作 
public:void bfsOrder(std::deque<std::string> & res,void(*p)(std::deque<std::string>&, const T&))const	40-以广度优先搜索的方式遍历结点(带string双端队列的)
public:void bfsOrder(std::deque<std::string>& res,const char* searchKey,void(*p)(std::deque<std::string>&, const char*, const T&))	const
																										41-以广度优先搜索的方式遍历结点(带string双端队列与搜索关键字的)				通过p所指向的函数对遍历到的结点进行操作
public:void bfsOrder(std::deque<std::string>& res,std::deque<std::string>& searchQue,std::set<std::string>& repeat,void(*p)(std::deque<std::string>&,std::deque<std::string>&,std::set<std::string>&,const T&))const
																										42-以广度优先搜索的方式遍历结点(带string双端队列与搜索关键字string队列的)	通过p所指向的函数对遍历到的结点进行操作
public:void bfsOrder(std::ofstream& ofs,void(*p)(std::ofstream& ofs, const T&))const					43-以广度优先搜索的方式遍历结点(带文件流对象的)		通过p所指向的函数对遍历到的结点进行操作 
public:void bfsOrder(node newRoot,node nil,void(*p)(node,node,const T&))const							44-以广度优先搜索的方式遍历结点(带结点指针的)		通过p所指向的函数对遍历到的结点进行操作
public:static node insert_x(const T&x, node rt, node nil)												45-修复树平衡结构时用到的静态插入元素操作实现函数 
public:static void add(node newRoot, node nil, const T& ele)											46-修复树平衡结构时用到的静态插入元素操作驱动函数 
public:void fix(void)																					47-重建树以修复树平衡结构
public:AATreeZ<T>& fileOutPut(const char* filePath)const												48-以广度优先搜索的顺序将每一个节点的元素以二进制形式输出到文件  
public:friend std::ofstream& operator << (std::ofstream& ofs, const AATreeZ<T>&AABST)					49-广搜文件输出运算符重载 
public:AATreeZ<T>& fileInPut(const char* filePath)														50-从文件读入并建立AA-树函数 
public:friend std::ifstream& operator >> (std::ifstream& ifs, const AATreeZ<T>&AABST)					51-文件读入函数运算符重载 
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
protected:void makeEmpty_(node rt)																		03-清空树操作实现函数
protected:node&findPointer_(const T&x,node rt)const														07-寻找元素实现函数，返回其前趋结点地址
protected:node find_(const T&x,node rt)const															08-寻找元素实现函数，返回其所在结点的地址
protected:node& findMinPointer_(node rt) const															11-寻找最小元素，并返回其前趋结点地址
protected:node& findMaxPointer_(node rt) const															12-寻找最大元素，并返回其前趋结点地址
protected:node findMin_(node rt)const																	13-寻找最小元素，并返回其所在结点地址
protected:node findMax_(node rt)const																	14-寻找最大元素，并返回其所在结点地址
protected:static node singleL2R_(node rt)																17-旋转结点-从左向右单旋转
protected:static node singleR2L_(node rt)																18-旋转结点-从右向左单旋转
protected:static node Skew(node rt)																		19-平衡节点操作-AA树Skew
protected:static node Split(node rt)																	20-平衡节点操作-AA树Split
protected:node insert_(const T&x, node rt, T*& addressExist)											21-插入元素操作实现函数 
protected:node del_(const T&x,node rt,void(*funP)(const T&) = NULL,bool* deled = NULL)					24-删除元素操作实现函数
protected:void midOrder_(node rt,void(*p)(const T&))const												28-中序遍历操作实现函数								通过p所指向的函数对遍历到的结点进行操作 
protected:void midOrder_(std::ofstream & ofs,node rt,void(*p)(std::ofstream&, const T&))const			29-中序遍历操作实现函数(带文件流对象的)				通过p所指向的函数对遍历到的结点进行操作 
protected:void preOrder_(node rt,void(*p)(const T&))const												26-先序遍历操作实现函数								通过p所指向的函数对遍历到的结点进行操作 
protected:void postOrder_(node rt,void(*p)(const T&))const												32-后序遍历操作实现函数								通过p所指向的函数对遍历到的结点进行操作 
protected:void enLevel(node rt)																			34-重新计算当前结点的层次 
protected:void reLevel_(node rt)																		35-重新计算所有结点层次操作实现函数					注意，前提是当前二叉树原本结构符合AA-树平衡条件
*/
				public:typedef	  AANode<T> Node;	//将结点结构体类型定义为Node
				public:typedef	  Node*	    node;	//将结点结构体的指针定义为node
				
				public:void 	  (*co_destructor)(const T&);
				
				protected:node	  root;				//带头树根
				protected:node	  dptr;				//删除函数辅助变量
				protected:node	  last;				//删除函数辅助变量
/*
我们的每一个AA-树对象，树根结点不存储任何元素，用于在内存中固定树的入口地址在我
们的实现中，根的右子结点充当接地(Nil)结点，根的左子结点才是存储元素的起始根结点
Nil的左右子结点都指向自己。空树的根的左子结点也指向Nil。所有叶子结点的左右子结点
都指向Nil。所以代码中出现的root->rChild其实都是Nil。每一颗不同的AA-树有自己
不同于其它树的Nil结点。

注意:Nil结点的层次 level 为 0。
*/
				
				public:template<class itr_type> class itr:public std::iterator//迭代器抽象基类 
				<
					std::forward_iterator_tag, 
					T,	long, 
					T*,	T&
				>
				{
					friend class AATreeZ<T>;
					protected:node now;
					protected:node nil;
					
                    public:itr(void):now(NULL), nil(NULL){}
					public:itr(const itr& another):
                    now(another.now), nil(another.nil){}
					
					public:virtual itr_type& operator = (const itr_type& another) = 0;
					
					public:bool operator == (const itr& another) const
					{
						return now == another.now;
					}
					
					public:bool operator != (const itr& another) const
					{
						return now != another.now;
					}
					
					public:virtual itr_type& operator ++ (void) = 0;
					
					public:operator T* (void) const
					{
						return &(now->element);
					}
					
					public:T* operator -> (void) const
					{
						return &(now->element);
					}
				};
				
				public:class bfs_iterator:public itr<bfs_iterator>	//层序迭代器
				{
					friend class AATreeZ<T>;
					protected:std::queue<node> que;
					
                    public:bfs_iterator(void):itr<bfs_iterator>(){}
					public:bfs_iterator(const bfs_iterator& another):
					itr<bfs_iterator>(another), que(another.que){}
					
					private:static void clrque(std::queue<node>& que)
					{
						std::queue<node> empty;
						swap(empty, que);
					}
					
					public:bfs_iterator& operator = (const bfs_iterator& another)
					{
						itr<bfs_iterator>::now = another.now;
						itr<bfs_iterator>::nil = another.nil;
						clrque(que);
						que = another.que;
						
						return *this;
					}
					
					public:bfs_iterator& operator ++ (void)
					{
						if(que.empty())
						{
							itr<bfs_iterator>::now = itr<bfs_iterator>::nil;
							return *this;
						}
						
						itr<bfs_iterator>::now = que.front();
						que.pop/*_front*/();
						
						if(itr<bfs_iterator>::now->lChild != itr<bfs_iterator>::nil) que.push/*_back*/(itr<bfs_iterator>::now->lChild);
						if(itr<bfs_iterator>::now->rChild != itr<bfs_iterator>::nil) que.push/*_back*/(itr<bfs_iterator>::now->rChild);
						
						return *this;
					}
				};
				
				public:typedef bfs_iterator iterator;
				
				public:class mid_iterator:public itr<mid_iterator>	//中序迭代器 
				{
					friend class AATreeZ<T>;
					protected:std::stack<node>	stk;
					private:bool				isFirst;
					
                    public:mid_iterator(void):itr<mid_iterator>(), isFirst(false){}
					public:mid_iterator(const mid_iterator& another):
					itr<mid_iterator>(another), stk(another.stk), isFirst(false)
					{
						if(another.isFirst)
							++(*this);
					}
					
					private:static void clrstk(std::stack<node>& stk)
					{
						std::stack<node> empty;
						swap(empty, stk);
					}
					
					public:mid_iterator& operator = (const mid_iterator& another)
					{
						itr<mid_iterator>::now = another.now;
						itr<mid_iterator>::nil = another.nil;
						clrstk(stk);
						stk = another.stk;
						
						if(another.isFirst)
							++(*this);
						isFirst = false;
						
						return *this;
					}
					
					public:bool hasNext(void)
					{
						return !(stk.size() == 1  &&  itr<mid_iterator>::now->rChild == itr<mid_iterator>::nil);
					}
					
					public:mid_iterator& operator ++ (void)
					{
						if(stk.empty())
						{
							itr<mid_iterator>::now = itr<mid_iterator>::nil;
							return *this;
						}
						
						itr<mid_iterator>::now = stk.top();
						
						while(itr<mid_iterator>::now != itr<mid_iterator>::nil)
						{
							stk.push(itr<mid_iterator>::now->lChild);
							itr<mid_iterator>::now = itr<mid_iterator>::now->lChild;
						}
						
						stk.pop();
						
						if(stk.empty())
						{
							itr<mid_iterator>::now = itr<mid_iterator>::nil;
							return *this;
						}
						
						itr<mid_iterator>::now = stk.top();
						stk.pop();
						stk.push(itr<mid_iterator>::now->rChild);
						
						return *this;
					}
				};
				
				protected:iterator op, ed;
				protected:mid_iterator mop, med;
				
				public:AATreeZ(void):co_destructor(NULL), //01-构造函数
				root(new Node), dptr(NULL), last(NULL)
				{
					root->rChild = new Node;//Nil
					root->lChild = root->rChild;
					root->rChild->level = 0;
					root->rChild->lChild = root->rChild;
					root->rChild->rChild = root->rChild;
					last = dptr = root->rChild;
					
					mop.now = op.now = root->lChild;
					mop.nil = op.nil = root->rChild;
																									//
					mop.stk.push(root->lChild);
					if(root->lChild->lChild != root->rChild)
						op.que.push(root->lChild->lChild);
					if(root->lChild->rChild != root->rChild)
						op.que.push(root->lChild->rChild);
					med.now = ed.now = root->rChild;
					
					mop.isFirst = true;
				}
				
				public:iterator begin(void) const
				{
					return op;
				}
				
				public:iterator end(void) const
				{
					return ed;
				}
				
				public:mid_iterator mid_begin(void) const
				{
					return mop;
				}
				
				public:mid_iterator mid_end(void) const
				{
					return med;
				}
				
				//02-判断树是否为空
				public:bool isEmpty(void)const
				{
					return root->lChild==root->rChild;
				}
				
				//03-清空树操作实现函数
				protected:void makeEmpty_(node rt)
				{
					if(rt != root->rChild)//后序遍历
					{
						makeEmpty_(rt->lChild);
						makeEmpty_(rt->rChild);
						delete rt;
					}
				}
				
				//03'-清空树操作实现函数(带协析构器)
				protected:void makeEmpty_co_des(node rt)
				{
					if(rt != root->rChild)//后序遍历
					{
						makeEmpty_co_des(rt->lChild);
						makeEmpty_co_des(rt->rChild);
						co_destructor(rt->element);
						delete rt;
					}
				}
				
				//04-清空树操作驱动函数&外部接口
				public:void makeEmpty(void)
				{
					if(co_destructor != NULL)
						makeEmpty_co_des(root->lChild);
					else makeEmpty_(root->lChild);
					root->lChild = root->rChild;
				}
				
				//05-清空树对象运算符重载
				public:void operator ~ (void)
				{
					makeEmpty();
				}
				
				//06-析构函数，释放空间
				public:virtual ~AATreeZ(void)
				{
					makeEmpty();
					delete root->rChild;
					delete root;
				}
				
				//07-寻找元素实现函数，返回其前趋结点地址
				protected:node&findPointer_
				(const T&x,node rt)const
				{
					node*p = NULL;
					while(rt != root->rChild)
					{
						if(x<rt->element)
						{
							p = &rt->lChild;
							rt = rt->lChild;
						}
						else if(x>rt->element)
						{
							p = &rt->rChild;
							rt = rt->rChild;
						}
						else
							break;
					}
					return*p;
				}
				
				//08-寻找元素实现函数，返回其所在结点的地址
				protected:node find_
				(const T&x,node rt)const
				{
					while(rt != root->rChild)
					{
						if(x<rt->element)
							rt = rt->lChild;
						else if(x>rt->element)
							rt = rt->rChild;
						else
							break;
					}
					if(rt != root->rChild) return rt;
					else return NULL;
				}
				
				//09-寻找元素驱动函数，返回其引用
				public:T& find(const T&x) const
				{
					return find_(x,root->lChild)->element;
				}
				
				public:T* find_ptr(const T&x) const
				{
					return &(find_(x,root->lChild)->element);
				}
				
				//10-寻找元素运算符重载，返回其地址 ，元素未找到返回NULL 
				public:T* operator [] (const T&x) const
				{
					node ret;
					ret = find_(x,root->lChild);
					
					if(ret != NULL) return &ret->element;
					else return NULL;
				}
				
				//11-寻找最小元素，并返回其前趋结点地址
				protected:node& findMinPointer_(node rt) const
				{
					node*p = NULL;
					while(rt->lChild != root->rChild)
					{
						p = &rt->lChild;
						rt = rt->lChild;
					}
					return*p;
				}
				
				//12-寻找最大元素，并返回其前趋结点地址
				protected:node& findMaxPointer_(node rt) const
				{
					node*p = NULL;
					while(rt->rChild!=root->rChild)
					{
						p = &rt->rChild;
						rt = rt->rChild;
					}
					return*p;
				}
				
				//13-寻找最小元素，并返回其所在结点地址
				protected:node findMin_(node rt)const
				{
					while(rt->lChild!=root->rChild)
						rt = rt->lChild;
					return rt;
				}
				
				//14-寻找最大元素，并返回其所在结点地址
				protected:node findMax_(node rt)const
				{
					while(rt->rChild!=root->rChild)
						rt = rt->rChild;
					return rt;
				}
				
				//15-寻找最小元素，并返回其引用
				public:T&findMin(void)const
				{
					return findMin_(root->lChild)->element;
				}
				
				//16-寻找最大元素，并返回其引用
				public:T&findMax(void)const
				{
					return findMax_(root->lChild)->element;
				}
				
				//17-旋转结点-从左向右单旋转 
				protected:static node singleL2R_(node rt)//LL
				{
					node ret = rt->lChild;
					rt->lChild = ret->rChild;
					ret->rChild = rt;
					
					return ret;
				}
				
				//18-旋转结点-从右向左单旋转 
				protected:static node singleR2L_(node rt)//RR
				{
					node ret = rt->rChild;
					rt->rChild = ret->lChild;
					ret->lChild = rt;
					
					return ret;
				}
				
				//19-平衡节点操作-AA树Skew 
				protected:static node Skew(node rt)
				{
					//如果左子树与当前结点的层次相同 
					if(rt->lChild->level == rt->level)
					{
						//设当前结点为当前子树根结点 
						//让前子树根结点的左子节点成为当前子树的新根节点
						rt = singleL2R_(rt);
					}
					return rt;
				}
				
				//20-平衡节点操作-AA树Split 
				protected:static node Split(node rt)
				{
					//如果出现连续的右水平链接 
					if(rt->rChild->rChild->level == rt->level)
					{
						//使当前节点的右子结点成为当前子树新根
						//并上移新根结点的层次 
						rt = singleR2L_(rt);
						++rt->level;
					}
					return rt;
				}							
				
				protected:node insert_//21-插入元素操作实现函数 
				(const T&x, node rt, T*& addressExist)
				{
					if(rt == root->rChild)//到达叶子结点以后的空结点(Nil)
					{
						rt = new Node;
						rt->lChild = rt->rChild = root->rChild;
						rt->element = x;
					}
					else if(x<rt->element)//如果要插入的元素小于当前结点 
						rt->lChild =//向左子树递归 
							insert_(x,rt->lChild, addressExist);				
					else if(x>rt->element)//如果要插入的元素大于当前结点 
						rt->rChild =//向右子树递归 
							insert_(x,rt->rChild, addressExist);	
					else addressExist = &rt->element;
					//上面都是普通二叉排序树的递归插入过程
					
					rt = Split(Skew(rt)); //节点平衡检查与调整(自底向上对于递归每一层)
					
					return rt;
				}
				
				//22-插入元素操作驱动函数	若插入成功，返回NULL，如果待插入的元素已存在，返回其地址 
				public:T* insert(const T&x)
				{
					T *added = NULL;
					root->lChild = insert_(x, root->lChild, added);
					
					mop.now = op.now = root->lChild;
					iterator::clrque(op.que);
					mid_iterator::clrstk(mop.stk);
					
					mop.stk.push(root->lChild);
					if(root->lChild->lChild != root->rChild)
						op.que.push(root->lChild->lChild);
					if(root->lChild->rChild != root->rChild)
						op.que.push(root->lChild->rChild);
					
					return added;
				}
				
				//23-插入元素操作运算符重载		注意这里返回的是本对象的引用 
				public:AATreeZ<T>& operator << (const T& t)
				{
					insert(t);
					return *this;
				}
				
				//24-删除元素操作实现函数 
				protected:node del_
				(
					const T&x,
					node rt, 
					void(*funP)(const T&) = NULL,	/*删除结点前的额外操作*/
					bool* deled = NULL				/*是否删除了一个元素*/
				)
				{
					if(rt!=root->rChild)//如果未到达Nil结点(即当前递归的rt不是Nil)
					{
						last = rt;//使得last指针指向当前结点 
						if(x < rt->element)//当要删除的结点元素小于当前结点元素 
							rt->lChild = del_(x,rt->lChild, funP, deled);//向左子树递归 
						else//否则 （如果到达待删除元素的结点，或大于待删除元素结点） 
						{
							dptr = rt;//使得dptr指针指向当前结点 
							rt->rChild = del_(x,rt->rChild, funP, deled);//向右子树递归 
						}
						
						//经过上面巧妙的递归，dptr指针应该指向待删除的结点last指针应该指向待删除结点的值后继(其结点右子树最小元素) 
						//以下是递归的回溯部分(自底向上)
						
						if(rt == last)//如果回溯到待删除元素结点的值后继结点 
						{
							if(dptr!=root->rChild && x==dptr->element)//如果dptr正确地指向了待删除结点 
							{
								//交换dptr结点和last结点的元素数据
								/*这里，《数据结构与算法分析 ——C语言描述》是用last结点的元素覆盖掉dptr结点的元素，但是我们后来
								  的titleInd对象，在结点中存储的是指向手动内存分配得到的内存空间，如果直接覆盖指针，则会造成内存
								  泄漏，并且delete掉不应该delelte的原本待删除元素值后继元素所指向的空间，造成严重BUG 
								*/ 
								T swapTmp = dptr->element;
								dptr->element = rt->element;
								last->element = swapTmp;
							
								//删除结点前针对结点元素可以自定义一些操作(通过函数指针p所传入) 
								if(funP != NULL)
									funP(rt->element);
							
								/*因为原本待删除元素的值后继的位置上不可能有左子节点(因为它是待删除元素结点右子树中最小，最靠左的元素)，
								  那么只需要将其(原本待删除元素的值后继的位置上的结点)父结点的rChild指针跨过它，指向它的rChild指向的结点，
								  然后释放掉它的空间就好了 
								*/ 
								dptr = root->rChild;
								rt = rt->rChild;
								delete last;
								if(deled != NULL) *deled = true;	//向外反馈已删除一个结点
							}
						}
						else if//调整结点层次 
						(
							rt->level > rt->lChild->level+1 ||		//如果删除元素以后出现断层 
							rt->level > rt->rChild->level+1
						)
						{
							if((--rt->level) < rt->rChild->level)	//下放当前结点层次 
								rt->rChild->level = rt->level;
							
							//下面是一波玄学通用的玄学操作，具体不好解释，要画图
							//总的来说就是先拉直，然后重新分层 
							
							//拉直 
							rt = Skew(rt);
							rt->rChild = Skew(rt->rChild);
							rt->rChild->rChild = Skew(rt->rChild->rChild);
						
							//重新分层 
							rt = Split(rt);
							rt->rChild = Split(rt->rChild);
						}
					}
					//很重要，返回当前结点的地址。这里的rt可能是经过Skew/Split调整过的子树的新根，参考
					//递归调用语句 rt->lChild = del_(x,rt->lChild, funP); 与 rt->rChild = del_(x,rt->rChild, funP);
					return rt;
				}
				
				//25-删除元素驱动函数	删除是否成功通过deled所指向的布尔变量给出 
				public:AATreeZ<T>& del
				(
					const T& x,
					void(*funP)(const T&) = NULL,
					bool* deled = NULL
				)
				{
					last = dptr = root->rChild;
					root->lChild = del_(x,root->lChild, funP, deled);
					
					mop.now = op.now = root->lChild;
					iterator::clrque(op.que);
					mid_iterator::clrstk(mop.stk);
					mop.stk.push(root->lChild);
					if(root->lChild->lChild != root->rChild)
						op.que.push(root->lChild->lChild);
					if(root->lChild->rChild != root->rChild)
						op.que.push(root->lChild->rChild);
					
					return *this;
				}
				
				/*
				protected:T delLMin_(node rt)
				{
					if(rt==root->rChild || rt==NULL)
						return rt;
					
					last = rt;
					if(rt->lChild != root->rChild)
						rt->lChild = delLMin_(rt->lChild);
					else
					{
						dptr = rt;
						rt->rChild = delLMin_(rt->rChild);
					}
					
					if(rt == last)
					{
						if(rt!=root->rChild && x==dptr->element)
						{
							//删除结点前针对结点元素可以自定义一些操作
							if(funP != NULL)
								funP(rt->element);
							
							//删除结点
							dptr->element = rt->element;
							dptr = root->rChild;
							rt = rt->rChild;
							delete last;
							*deled = true;	//向外反馈已删除一个结点
						}
					}
					else if
					(
						rt->level > rt->lChild->level+1 ||
						rt->level > rt->rChild->level+1
					)
					{
						if((--rt->level) < rt->rChild->level)
							rt->rChild->level = rt->level;
							
						rt = Skew(rt);
						rt->rChild = Skew(rt->rChild);
						rt->rChild->rChild = Skew(rt->rChild->rChild);
						
						rt = Split(rt);
						rt->rChild = Split(rt->rChild);
					}
					
					return rt;
				}	
				
				public:AATreeZ<T>& operator >> (T& t)
				{
					t = delLMin_(root->lChild);
					return *this;
				}
				*/
				
/*
				protected:void preOrder_//26-先序遍历操作实现函数	通过p所指向的函数对遍历到的结点进行操作 
				(node rt,void(*p)(const T&))const
				{
					if(p != NULL)
					{
						p(rt->element);
						if(rt->lChild != root->rChild)
							preOrder_(rt->lChild,p);
						if(rt->rChild != root->rChild)
							preOrder_(rt->rChild,p);
					}
				}
				
*/
				//27-先序遍历操作驱动函数 
				public:void preOrder(void(*p)(const T&))const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
					
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
						{
							p(tmp->element);
							stk.push(tmp->lChild);
						}
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
/*
				protected:void midOrder_//28-中序遍历操作实现函数
				(node rt,void(*p)(const T&))const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(rt->lChild,p);
						p(rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(rt->rChild,p);
					}
				}
				
				//29-带文件流对象的中序遍历操作实现函数
				protected:void midOrder_
				(
					std::ofstream & ofs,
					node rt,void(*p)(std::ofstream&, const T&)
				)const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(ofs, rt->lChild,p);
						p(ofs, rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(ofs, rt->rChild,p);
					}
				}
				
*/
				//30-中序遍历操作驱动函数
				public:void midOrder(void(*p)(const T&))const
				{
					//midOrder_(root->lChild,p);
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				//31-带文件流对象的中序遍历操作驱动函数
				public:void midOrder
				(
					std::ofstream &ofs,
					void(*p)(std::ofstream&, const T&)
				)	const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(ofs, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				public:void midOrder
				(
					std::ostream &ofs,
					void(*p)(std::ostream&, const T&)
				)	const
				{
					node tmp;	
					std::stack<node> stk;
					stk.push(root->lChild);		
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(ofs, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
/*
				protected:void midOrder_
				(
					std::deque<std::string>& res,
					node rt, void(*p)(std::deque<std::string>& res, const T&)
				)	const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(res, rt->lChild,p);
						p(res, rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(res, rt->rChild,p);
					}
				}
				
				public:void midOrder
				(
					std::deque<std::string>& res,
					void(*p)(std::deque<std::string>&,const T&)
				)	const
				{
					if(root->lChild == root->rChild)
						return;
					
					midOrder_(res, root->lChild, p);
				}
				*/
				public:void midOrder
				(
					std::set<std::string>& res,
					void(*p)(std::set<std::string>&,const T&)
				)	const
				{
					if(root->lChild == root->rChild)
						return;
					
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(res, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				/*
				protected:void midOrder_
				(
					std::set<std::string>& res,
					node rt,void(*p)(std::set<std::string>& res, const T&)
				)const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(res, rt->lChild,p);
						p(res, rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(res, rt->rChild,p);
					}
				}
				
*/
				
				
				public:void midOrder
				(
					std::deque<std::string>& res,
					void(*p)(std::deque<std::string>&,const T&)
				)	const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(res, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				public:void midOrder
				(
					std::deque<std::string>& res,
					void(*p)(std::deque<std::string>&, const T&, void* obj),
					void* obj
				)	const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(res, stk.top()->element, obj);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				//32-后序遍历操作实现函数
				protected:void postOrder_
				(node rt,void(*p)(const T&))const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							postOrder_(rt->lChild,p);
						if(rt->rChild != root->rChild)
							postOrder_(rt->rChild,p);
						p(rt->element);
					}
				}
				
				//33-后序遍历操作驱动函数
				public:void postOrder(void(*p)(const T&))const
				{
					postOrder_(root->lChild,p);
				}
				
				//34-重新计算当前结点的层次 
				protected:void enLevel(node rt)
				{
					rt->level = rt->lChild->level+1;
					if(rt->level < rt->rChild->level)
						rt->level = rt->rChild->level;
					if(rt->level <= rt->rChild->rChild->level)
						rt->level = rt->rChild->rChild->level+1;
				}
				
				//35-重新计算所有结点层次操作实现函数		注意，前提是当前二叉树原本结构符合AA-树平衡条件 
				protected:void reLevel_(node rt)
				{
					if(rt->lChild != root->rChild)
						reLevel_(rt->lChild);
					if(rt->rChild != root->rChild)
						reLevel_(rt->rChild);
					enLevel(rt);
				}
				
				//36-重新计算所有结点层次操作驱动函数		注意，前提是当前二叉树原本结构符合AA-树平衡条件 
				public:void reLevel(void)
				{
					reLevel_(root->lChild);
					mop.now = op.now = root->lChild;
					iterator::clrque(op.que);
					mid_iterator::clrstk(mop.stk);
					mop.stk.push(root->lChild);
					if(root->lChild->lChild != root->rChild)
						op.que.push(root->lChild->lChild);
					if(root->lChild->rChild != root->rChild)
						op.que.push(root->lChild->rChild);
				}
				
				//37-不带平衡旋转的节点插入函数		适用于从以BFS的方式遍历已平衡的AA-树结点元素输出的文件中读取元素并重建AA-树
				/*
				若使用BFS算法的顺序遍历已经过平衡操作的AA-树结点，将它们保存的元素输出到文件当中，则从文件当中重新读取元素时
				可以用循环编写插入操作，不必执行任何平衡旋转，只需重新计算每个结点的层次。这样会省下不少时间。 
				*/ 
				public:void insertWithoutEnbalance(const T& ele)
				{
					node rt = root->lChild;
					node *tmp=&root->lChild;
					if(rt==root->rChild)
					{
						rt = new Node;
						rt->lChild = rt->rChild = root->rChild;
						rt->level = 1;
						rt->element = ele;
						*tmp = rt;
					}
	
					while(rt!=root->rChild && rt->element!=ele)
					{
						if(ele<rt->element)
						{
							tmp=&(rt->lChild);
							rt=rt->lChild;
						}
						else
						{
							tmp=&(rt->rChild);
							rt=rt->rChild;
						}
					}
					
					if(rt==root->rChild)
					{
						*tmp = rt = new Node;
						rt->lChild = rt->rChild = root->rChild;
						rt->level = 1;
						rt->element = ele;
					}
				}
				
				//38-以广度优先搜索的方式遍历结点 
				public:void bfsOrder(void(*p)(const T&))const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(now->element);
#ifdef TEST
				std::cout<<", Level:"<<int(now->level)<<std::endl;
#endif
					}
				}
				
				//39-以广度优先搜索的方式遍历结点(带char*双端队列的)
				public:void bfsOrder
				(
					std::deque<char *> & que,
					void(*p)(std::deque<char *>&, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(que, now->element.address);
					}
				}
				
				//40-以广度优先搜索的方式遍历结点(带string双端队列的)
				public:void bfsOrder
				(
					std::deque<std::string> & res,
					void(*p)(std::deque<std::string>&, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, now->element.address);
					}
				}
				
				public:void bfsOrder
				(
					std::set<std::string> & res,
					void(*p)(std::set<std::string>&, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, now->element.address);
					}
				}
				
				//41-以广度优先搜索的方式遍历结点(带string双端队列与搜索关键字的)
				public:void bfsOrder
				(
					std::deque<std::string>& res,
					const char* searchKey,
					void(*p)(std::deque<std::string>&, const char*, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, searchKey, now->element);
					}
				}
				
				
/*
				protected:void midOrder_
				(
					std::deque<std::string>& res, const char* searchKey,
					node rt, void(*p)(std::deque<std::string>&, const char*, const T&)
				)const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(res, searchKey, rt->lChild,p);
						p(res, searchKey, rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(res, searchKey, rt->rChild,p);
					}
				}
				
*/
				
				public:void midOrder
				(
					std::deque<std::string>& res,
					const char* searchKey,
					void(*p)(std::deque<std::string>&, const char*, const T&)
				)	const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(res, searchKey, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				public:void bfsOrder
				(
					std::set<std::string>& res,
					const char* searchKey,
					void(*p)(std::set<std::string>&, const char*, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, searchKey, now->element);
					}
				}
				
				//42-以广度优先搜索的方式遍历结点(带string双端队列与搜索关键字string队列的)
				public:void bfsOrder
				(
					std::deque<std::string>& res,
					std::deque<std::string>& searchQue,
					std::set<std::string>& repeat,
					void(*p)
					(
						std::deque<std::string>&, 
						std::deque<std::string>&, 
						std::set<std::string>&,
						const T&
					)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, searchQue, repeat, now->element);
					}
				}
				
				/*
				protected:void midOrder_
				(
					std::deque<std::string>& res, 
					std::deque<std::string>& searchQue, 
					std::set<std::string>& repeat,
					node rt, 
					void(*p)
					(
						std::deque<std::string>&, 
						std::deque<std::string>&, 
						std::set<std::string>&,
						const T&
					)
				)const
				{
					if(p != NULL)
					{
						if(rt->lChild != root->rChild)
							midOrder_(res, searchQue, repeat, rt->lChild,p);
						p(res, searchQue, repeat, rt->element);
						if(rt->rChild != root->rChild)
							midOrder_(res, searchQue, repeat, rt->rChild,p);
					}
				}
				
*/
				
				public:void midOrder
				(
					std::deque<std::string>& res,
					std::deque<std::string>& searchQue,
					std::set<std::string>& repeat,
					void(*p)
					(
						std::deque<std::string>&, 
						std::deque<std::string>&, 
						std::set<std::string>&,
						const T&
					)
				)	const
				{
					std::stack<node> stk;
					stk.push(root->lChild);
			
					node tmp;			
					while(!stk.empty())
					{
						tmp = stk.top();
						if(tmp != root->rChild)
							stk.push(tmp->lChild);
						else
						{
							stk.pop();
							if(stk.empty())
								break;
							p(res, searchQue, repeat, stk.top()->element);
							tmp = stk.top();
							stk.pop();
							stk.push(tmp->rChild);
						}
					}
				}
				
				public:void bfsOrder
				(
					std::set<std::string>& res,
					std::deque<std::string>& searchQue,
					void(*p)
					(
						std::set<std::string>&, 
						std::deque<std::string>&, 
						const T&
					)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(res, searchQue, now->element);
					}
				}
				
				//43-以广度优先搜索的方式遍历结点(带文件流对象的)
				public:void bfsOrder
				(
					std::ofstream& ofs, 
					void(*p)(std::ofstream& ofs, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(ofs, now->element);
					}
				}
				
				//44-以广度优先搜索的方式遍历结点(带结点指针的)
				public:void bfsOrder
				(
					node newRoot, 
					node nil,
					void(*p)(node, node, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(newRoot, nil, now->element);
					}
				}
				
				/*
				protected:static node insert_
				(const T&x, node rt, T*& addressExist)
				{
					if(rt == root->rChild)//到达叶子结点以后的空结点
					{
						rt = new Node;
						rt->lChild = rt->rChild = root->rChild;
						rt->element = x;
					}
					else if(x<rt->element)//L
						rt->lChild =
							insert_(x,rt->lChild, addressExist);				
					else if(x>rt->element)//R
						rt->rChild = 
							insert_(x,rt->rChild, addressExist);	
					else addressExist = &rt->element;
					
					rt = Split(Skew(rt));
					return rt;
				}
				
				public:T* insert(const T&x)
				{
					T *added = NULL;
					root->lChild = insert_(x,root->lChild,added);
					return added;
				}
				*/
				
				//45-修复树平衡结构时用到的静态插入元素操作实现函数 
				public:static node insert_x
				(const T&x, node rt, node nil)
				{
					if(rt == nil)//到达叶子结点以后的空结点
					{
						rt = new Node;
						rt->lChild = rt->rChild = nil;
						rt->element = x;
					}
					else if(x<rt->element)//L
						rt->lChild =
							insert_x(x, rt->lChild, nil);
					else if(x>rt->element)//R
						rt->rChild = 
							insert_x(x, rt->rChild, nil);
					
					rt = Split(Skew(rt));
					return rt;
				}
				
				//46-修复树平衡结构时用到的静态插入元素操作驱动函数 
				public:static void add
				(node newRoot, node nil, const T& ele)
				{
					newRoot->lChild = 
						insert_x(ele, newRoot->lChild, nil);
				}
				
				//47-重建树以修复树平衡结构 
				public:void fix(void)
				{
					//做一个新根并初始化它 
					node newRoot = new Node;
					newRoot->lChild = newRoot->rChild = new Node;
					newRoot->rChild->lChild = newRoot->rChild;
					newRoot->rChild->rChild = newRoot->rChild;
					
					//以平衡插入的方式，将旧树的所有元素插入到新树中 
					bfsOrder(newRoot, newRoot->rChild, add);
					
					//销毁旧树 
					makeEmpty();
					delete root->rChild;
					delete root;
					
					//令本对象的根指针指向新根 
					root = newRoot;
					
					mop.now = op.now = root->lChild;
					mop.nil = op.nil = root->rChild;
																									//
					mop.stk.push(root->lChild);
					if(root->lChild->lChild != root->rChild)
						op.que.push(root->lChild->lChild);
					if(root->lChild->rChild != root->rChild)
						op.que.push(root->lChild->rChild);
					med.now = ed.now = root->rChild;
					mop.isFirst = true;
				}
				
				//48-以广度优先搜索的顺序将每一个结点的元素以二进制形式输出到文件 
				public:AATreeZ<T>& fileOutPut
				(const char* filePath)const
				{
					std::ofstream ofs;
					
					//打开文件 
					try
					{
						ofs.open
						(
							filePath,
							std::ios_base::binary | std::ios_base::trunc
						);
						ofs.close();
						ofs.open
						(
							filePath,
							std::ios_base::binary | std::ios_base::app
						);
					}
					catch(...){throw(IOERROR);}
					
					//广搜遍历 
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						ofs.write//以二进制形式写入结点元素 
						(
							reinterpret_cast<char*>(&now->element),
							sizeof(T)
						);
					}
					
					//清空cache，关闭文件 
					try{ofs.close();}
						catch(...){throw(IOERROR);}
					
					return *this;
				}
				
				//49-广搜文件输出运算符重载 
				public:friend std::ofstream& operator << 
				(std::ofstream& ofs, const AATreeZ<T>&AABST)
				{
					std::queue<node> bfsQue;
					if(AABST.root->lChild != AABST.root->rChild)
						bfsQue.push(AABST.root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != AABST.root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != AABST.root->rChild)
							bfsQue.push(now->rChild);
						
						ofs.write
						(
							reinterpret_cast<char*>(&now->element),
							sizeof(T)
						);
					}
					
					return ofs;
				}
				
				//50-从文件读入并建立AA-树函数 
				public:AATreeZ<T>& fileInPut(const char* filePath)
				{
					makeEmpty();
					std::ifstream ifs;
					T t;
					
					try{ifs.open(filePath, std::ios_base::binary);}
						catch(...){throw(IOERROR);}
						
					while(!ifs.eof())
					{
						ifs.read(reinterpret_cast<char*>(&t),sizeof(T));
						insertWithoutEnbalance(t);
					}
					reLevel();
					
					try{ifs.close();}
						catch(...){throw(IOERROR);}
					return *this;
				}
				
				//51-文件读入函数运算符重载 
				public:friend std::ifstream& operator >>
				(std::ifstream& ifs, const AATreeZ<T>&AABST)
				{
                    AABST.makeEmpty();
					T t;
					
					while(!ifs.eof())
					{
						ifs.read(reinterpret_cast<char*>(&t),sizeof(T));
                        AABST.insertWithoutEnbalance(t);(t);
					}
					AABST.reLevel();
					return ifs;
				}
				//undef root->rChild
				
				public:void bfsOrder
				(
					const std::string& pth, 
					void(*p)(const std::string&, const T&)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(pth, now->element);
					}
				}
				
				public:void bfsOrder
				(
					const char* prop,
					const char* pth, 
					std::deque<std::string>& res,
					void(*p)
					(
						const char*, 
						const char*, 
						std::deque<std::string>&,
						const T&
					)
				)	const
				{
					if(p == NULL) return;
					std::queue<node> bfsQue;
					if(root->lChild != root->rChild)
						bfsQue.push(root->lChild);
					
					for(node now = NULL;!bfsQue.empty();)
					{
						now = bfsQue.front();
						bfsQue.pop();
						
						if(now->lChild != root->rChild)
							bfsQue.push(now->lChild);
						if(now->rChild != root->rChild)
							bfsQue.push(now->rChild);
						
						p(prop, pth, res, now->element);
					}
				}
				
				public:T* rootEle(void)
				{
					if(!isEmpty())
						return &root->lChild->element;
					else return NULL;
				}
				
			};
		};
	};
//};

//防止重复文件包含
#endif

/*
				public:class bfs_iterator:public itr//广搜迭代器
				{
					friend class AATreeZ<T>;
					protected:node now;
					protected:node nil;
					protected:std::queue<node> que;
					
                    public:iterator(void):now(NULL), nil(NULL){}
					public:iterator(const iterator& another):
                    now(another.now), nil(another.nil), que(another.que){}
					
					private:static void clrque(std::queue<node>& que)
					{
						std::queue<node> empty;
						swap(empty, que);
					}
					
					public:iterator& operator = (const iterator& another)
					{
						now = another.now;
						nil = another.nil;
						//que.clear();
						clrque(que);
						que.assign(another.que);
						
						return *this;
					}
					
					public:bool operator == (const iterator& another) const
					{
						return now == another.now;
					}
					
					public:bool operator != (const iterator& another) const
					{
						return now != another.now;
					}
					
					public:iterator& operator ++ (void)
					{
						if(que.empty())
						{
							now = nil;
							return *this;
						}
						
						now = que.front();
						que.pop();
						
						if(now->lChild != nil) que.push(now->lChild);
						if(now->rChild != nil) que.push(now->rChild);
						
						return *this;
					}
					
					public:operator T* (void) const
					{
						return &(now->element);
					}
				};
*/
